package songuyenlon;
import java.util.*;
public class SoNguyenLon {
	
    final int BASE = 1000000000;

    private int[] a;
    private int sophantu;

    public SoNguyenLon(){
        this.a = null;
        this.sophantu = 0;
    }

    public SoNguyenLon(String string){
        this.setA(Nhapsotuxau(string));
    }	

    public SoNguyenLon(int[] mc,int m){
        this.a = mc;
        this.sophantu = m;
    }

    public SoNguyenLon(long m){
        String string = Long.toString(m);
        this.setA(Nhapsotuxau(string));
    }

    public int[] getA(){
        return this.a;
    }

    public void setA(int[] ma){
        this.a = ma;
    }

    public int getSoPhanTu(){
        return this.sophantu;
    }

    public void setSoPhanTu(int sophantu){
        this.sophantu = sophantu;
    }

    /*
     * Chuyen tu xau ki tu sang so nguyen luu tru vao mang
     */

    private int[] Nhapsotuxau(String string){
        int m = string.length();
        int n = (m-1)/9 + 1;
        int[] ma = new int[n];
        int firstSome = m - 9*(n-1);

        for(int i=0;i<n;i++){
             String block = string.substring(Math.max(firstSome + (i-1)*9,0),firstSome + i*9);
             ma[i] = Integer.parseInt(block);
        }
        setSoPhanTu(n);
        return ma;
    }

    /*
     * In ra man hinh duoi dang xau ki tu
     */
    
    private String Xau(){
        Formatter f = new Formatter();
        f.format("%d", this.a[0]);
        for(int i = 1 ; i < getSoPhanTu(); i++) {
            f.format("%09d", this.a[i]);
        }
        return f.toString();
    }

    public void In(){
            String s = Xau();
            System.out.println(s);
    }

    /*
     * Phep cong 2 so nguyen lon
     */
    
    private void cong1(int[] ketqua, int phantu, int so){
        int sum = ketqua[phantu] + so;
        if(sum > BASE){
            ketqua[phantu] = sum-BASE;
            ketqua[phantu-1] += 1;
        }
        else{
            ketqua[phantu] = sum;
        }
    }

    private void cong2(int[] ketqua,int phantu,SoNguyenLon ma){
        int m = ma.getSoPhanTu() - 1;
        while(m>=0){
            cong1(ketqua,phantu,ma.a[m]);
            m--;
            phantu--;
        }
    }
    
    private void ganGiaTri(int[] ketqua, int phantu, SoNguyenLon ma){
    	int m = ma.getSoPhanTu() - 1;
    	while(m>=0){
            ketqua[phantu] = ma.a[m];
            m--;
            phantu--;
        }
    }

    public SoNguyenLon Cong(SoNguyenLon that){
    	if(this.a[0] >= 0){
    		if(that.a[0] >= 0){
    			int m = Math.max(this.getSoPhanTu(),that.getSoPhanTu());
    	        int[] mc = new int[m+1];
    	        ganGiaTri(mc, m, this);
    	        cong2(mc, m, that);
    	        if(mc[0] == 0){
    	            mc = Arrays.copyOfRange(mc, 1, m+1);
    	            m -= 1;
    	        }
    	        return new SoNguyenLon(mc,m+1);
    		}
    		else{
    			that.a[0] = -that.a[0];
    			return this.Tru(that);
    		}
    	}
    	else{
    		if(that.a[0] >= 0){
    			this.a[0] = -this.a[0];
    			return that.Tru(this);
    		}
    		else{
    			this.a[0] = this.a[0];
    			that.a[0] = -that.a[0];
    			int m = Math.max(this.getSoPhanTu(),that.getSoPhanTu());
    	        int[] mc = new int[m+1];
    	        ganGiaTri(mc,m,this);
    	        cong2(mc,m,that);
    	        if(mc[0] == 0){
    	            mc = Arrays.copyOfRange(mc, 1, m+1);
    	            m -= 1;
    	        }
    	        mc[0] = -mc[0];
    	        return new SoNguyenLon(mc,m+1);
    		}
    	}
    }

    /*
     * Phep nhan 2 so nguyen lon
     */

    private void nhan1(int[] ketqua, int phantu, int so1, int so2){
        long m1 = (long)so1 * (long)so2;
        int m2 = (int)(m1%BASE);
        cong1(ketqua,phantu,m2);
        int nho = (int)(m1/BASE);
        cong1(ketqua,phantu-1,nho);
    }

    private void nhan2(int[] ketqua, int phantu, SoNguyenLon ma, SoNguyenLon mb){
        for(int i=ma.getSoPhanTu()-1;i>=0;i--) {
            for(int j=mb.getSoPhanTu()-1;j>=0;j--){
                nhan1(ketqua,i+j+1,ma.a[i],mb.a[j]);
            }
        }
    }

    public SoNguyenLon Nhan(SoNguyenLon that){
        int m = this.getSoPhanTu() + that.getSoPhanTu();
        int[] mc = new int[m];
        nhan2(mc,m-1,this,that);
        if(mc[0] == 0){
            mc = Arrays.copyOfRange(mc,1,m);
            m -= 1;
        }
        return new SoNguyenLon(mc,m);
    }

    /*
     * Phep tru 2 so nguyen lon
     */

    private void tru1(int[] ketqua, int phantu, int so){
        int sub = ketqua[phantu] - so;
        if(sub < 0){
            ketqua[phantu] = BASE + sub;
            tru1(ketqua,phantu-1,1);
        }
        else
            ketqua[phantu] = sub;
    }

    private void tru2(int[] ketqua,int phantu,SoNguyenLon ma){
        int m = ma.getSoPhanTu()-1;
        while(m >= 0){
            tru1(ketqua,phantu,ma.a[m]);
            m--;
            phantu--;
        }
    }

    public SoNguyenLon Tru(SoNguyenLon that){
        if(this.Sosanh(that) == 1){
            int m = this.getSoPhanTu();
            int[] mc = new int[m];
            ganGiaTri(mc,m-1,this);
            tru2(mc,m-1,that);
            for(int i=0;i<m;i++){
                if(mc[i] != 0){
                    mc = Arrays.copyOfRange(mc, i, m);
                    m = m - i;
                    return new SoNguyenLon(mc,m);
                }
            }	
        }
        else if(this.Sosanh(that) == -1){
            int m = that.getSoPhanTu();
            int[] mc = new int[m];
            ganGiaTri(mc,m-1,that);
            tru2(mc,m-1,this);
            for(int i=0;i<m;i++)
                if(mc[i] != 0){
                    mc = Arrays.copyOfRange(mc, i, m);
                    m = m - i;
                    mc[i] = - mc[i];
                    return new SoNguyenLon(mc,m);
                }
        }
        int[] mc = new int[1];
        mc[0] = 0;
        return new SoNguyenLon(mc,1);

    }

    /*
     * Phep chia 2 so nguyen lon
     */

    private int chia1(int[] ketqua, int phantu, int sochia, int du, int sobichia){
        long value = sochia + du*(long)BASE;
        ketqua[phantu] = (int) (value/sobichia);
        return (int) (value%sobichia);	
    }

    private int chia2(int[] ketqua, int phantu, SoNguyenLon ma, int sobichia){
        int sodu = 0;
        int i = 0;
        for(;i<ma.getSoPhanTu();i++,phantu++){
            sodu = chia1(ketqua,phantu,ma.a[i],sodu,sobichia);
        }
        return sodu;
    }

    private SoNguyenLon chia3(SoNguyenLon that){
        int m = this.getSoPhanTu();
        int[] mc = new int[m];
        chia2(mc,0,this,that.a[0]);
        if(mc[0] == 0){
            mc = Arrays.copyOfRange(mc,1,m);
            m -= 1;
        }
        return new SoNguyenLon(mc,this.getSoPhanTu());
    }

    private SoNguyenLon chia4(SoNguyenLon that){
        if(this.Sosanh(that) == 1){

            int m = this.getSoPhanTu() - that.getSoPhanTu() + 1;
            int[] mc = new int[m];

            int[] md = new int[this.getSoPhanTu()];
            for(int i=0;i<that.getSoPhanTu();i++)
                md[i] = that.a[i];

            SoNguyenLon A1 = this;
            SoNguyenLon A2 = new SoNguyenLon(md,this.getSoPhanTu());

            while(A1.Sosanh(A2) != -1){
                mc[0] = mc[0] + 1;
                A1 = A1.Tru(A2);
            }

            for(int i=0;i<m-1;i++){
                if(A1.getSoPhanTu() < that.getSoPhanTu())
                    return new SoNguyenLon(mc,mc.length);
                if(A1.a[0] == that.a[0])
                    mc[i+1] = BASE - 1;
                else
                    mc[i+1] = (int) ((A1.a[0]*(long) BASE + A1.a[1]) / that.a[0]);

                while( (long)(mc[i+1]*(that.a[0]*(long)BASE + that.a[1])) > (long)(A1.a[0]*(long)BASE*(long)BASE + A1.a[1]*(long)BASE + A1.a[2]) ){
                    mc[i+1] = mc[i+1] - 1;
                }

                md = new int[m - i - 1];
                md[0] = mc[i+1];
                A2 = new SoNguyenLon(md,m-i-1);
                A2 = A2.Nhan(that);

                if(A1.Sosanh(A2) != -1){
                    A1 = A1.Tru(A2);
                }
                else{
                    mc[i+1] = mc[i+1] - 1;
                    md = new int[m - i - 1];
                    md[0] = mc[i+1];
                    A2 = new SoNguyenLon(md,m-i-1);
                    A2 = A2.Nhan(that);
                    A1 = A1.Tru(A2);
                }	
            }	
            if(mc[0] == 0){
                mc = Arrays.copyOfRange(mc, 1, m+1);
                m -= 1;
            }
            return new SoNguyenLon(mc,m);
        }
        else{
            int m = 1;
            int[] mc = {0};
            return new SoNguyenLon(mc,m);
        }	
    }

    public SoNguyenLon Chia(SoNguyenLon that){
        if(that.getSoPhanTu() == 1)
            return this.chia3(that);
        else
            return this.chia4(that);
    }

    /*
     * Phep lay phan du
     */

    private SoNguyenLon phandu(SoNguyenLon that){
        if(this.Sosanh(that) == 1){

            int m = this.getSoPhanTu() - that.getSoPhanTu();
            int[] mc = new int[m];

            int[] md = new int[this.getSoPhanTu()];
            for(int i=0;i<that.getSoPhanTu();i++)
                    md[i] = that.a[i];

            SoNguyenLon A1 = this;
            SoNguyenLon A2 = new SoNguyenLon(md,this.getSoPhanTu());

            while(A1.Sosanh(A2) != -1){
                mc[0] = mc[0] + 1;
                A1 = A1.Tru(A2);
            }

            for(int i=0;i<m-1;i++){
                if(A1.getSoPhanTu() < that.getSoPhanTu())
                    break;
                if(A1.a[0] == that.a[0])
                    mc[i+1] = BASE - 1;
                else
                    mc[i+1] = (int) ((A1.a[0]*(long) BASE + A1.a[1]) / that.a[0]);

                while((long)(mc[i+1]*(that.a[0]*(long)BASE + that.a[1])) > (long)(A1.a[0]*(long)BASE*(long)BASE + A1.a[1]*(long)BASE + A1.a[2]) ){
                    mc[i+1] = mc[i+1] - 1;
                }

                md = new int[m - i - 1];
                md[0] = mc[i+1];
                A2 = new SoNguyenLon(md,m-i-1);
                A2 = A2.Nhan(that);

                if(A1.Sosanh(A2) != -1){
                    A1 = A1.Tru(A2);
                }
                else{
                    mc[i+1] = mc[i+1] - 1;
                    md = new int[m - i - 1];
                    md[0] = mc[i+1];
                    A2 = new SoNguyenLon(md,m-i-1);
                    A2 = A2.Nhan(that);

                    A1 = A1.Tru(A2);
                }	
            }	
            return A1;
        }
        else{
            return this;
        }	
    }

    public SoNguyenLon Phandu(SoNguyenLon that){
        if(that.getSoPhanTu() == 1){
            int m = 1;
            int[] mc = new int[m];
            int[] md = new int[this.getSoPhanTu()];
            mc[0] = chia2(md,0,this,that.a[0]);
            return new SoNguyenLon(mc,m);
        }
        else{
            return this.phandu(that);
        }
    }

    /*
     * So sanh hai so nguyen lon A1 va A2
     * Neu A1>A2 thi tra ve 1
     * Neu A1=A2 thi tra ve 0
     * Neu A1<A2 thi tra ve -1
     */

    public int Sosanh(SoNguyenLon that){
        if(this.getSoPhanTu() > that.getSoPhanTu())
            return 1;
        else if(this.getSoPhanTu() < that.getSoPhanTu())
            return -1;
        for(int i=0;i<this.getSoPhanTu();i++){
            if(this.a[i] > that.a[i])
                return 1;
            else if(this.a[i] < that.a[i])
                return -1;
        }
        return 0;
    }

    /*
     * Tinh do dai chu so cua so nguyen lon
     * Tra ve so chu so cua so nguyen lon duoi dang so nguyen
     */
    
    public int Dodai(){
        int m = 0;
        m = Integer.toString(this.a[0]).length() + (this.getSoPhanTu() - 1)*9;
        return m;
    }
}
